package com.zj.leetcode.medium.hash;

import java.util.HashMap;

/**
 * @program: algorithm
 * @description: 和为 K 的子数组
 * 560 subarray-sum-equals-k
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class SubarraySumEqualsK {
    public static void main(String[] args) {

//        int[] nums = {1,1,1,4};
//        int k = 2;

//        int[] nums = {1,2,1,2,1};
//        int k = 3;

//        int[] nums = {1};
//        int k = 0;

//        int[] nums = {0};
//        int k = 0;
        int[] nums = {1, -1, 0};
        int k = 0;
        Solution solution = new SubarraySumEqualsK().new Solution();

        System.out.println(solution.subarraySum(nums, k));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 穷举法，循环遍历
         *
         * @param nums
         * @param k
         * @return
         */
        public int subarraySum(int[] nums, int k) {

            if (nums.length < 1) {
                return 0;
            }
            int count = 0;
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                int temp = 0;
                for (int j = i; j < length; j++) {
                    temp += nums[j];
                    if (temp == k) {
                        count++;
                    }
                }
            }
            return count;

        }

        /**
         * 前缀和！！！
         * 永远滴神！
         *
         * @param nums
         * @param k
         * @return
         */
        public int subarraySum01(int[] nums, int k) {

            HashMap<Integer, Integer> map = new HashMap<>();

            int temp;
            for (int i = 0; i < nums.length; i++) {

            }
            return 0;

        }


        /**
         * 前缀和 来了
         *
         * @param nums
         * @param k
         * @return
         */
        public int subarraySum02(int[] nums, int k) {
            HashMap<Integer, Integer> map = new HashMap<>();

            int pre = 0;
            int count = 0;
            map.put(0, 1);
            for (int i = 0; i < nums.length; i++) {
                pre += nums[i];
                if (map.containsKey(pre - k)) {
                    count += map.get(pre - k);
                }
                map.put(pre, map.getOrDefault(pre, 0) + 1);
            }

            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
